package weekMatch.two_102;

import node.TreeNode;

import java.util.ArrayList;
import java.util.List;

public class LeeCode_03 {
    public static void main(String[] args) {
        replaceValueInTree(new TreeNode(3,new TreeNode(1), new TreeNode(2)));
    }
    private static TreeNode replaceValueInTree(TreeNode root) {
        int depth = getDepth(root, 0);
        List<List<Integer>> list = new ArrayList<>(depth);
        for (int i = 0; i < depth; i++) {
            list.add(new ArrayList<>());
        }
        dfs(list, root, 0);
        int[] sums = new int[depth];
        for (int i = 0; i < list.size(); i++) {
            List<Integer> lSon = list.get(i);
            int sum = 0;
            for (Integer num : lSon) {
                sum += num;
            }
            sums[i] = sum;
        }
        dfs2(list, root, 0, sums, root.val);
        return root;
    }
    private static void dfs2(List<List<Integer>> list, TreeNode node, int depth, int[] sums, int jian){
        if (node == null)
            return;
        node.val = sums[depth] - jian;
        int ln = node.left == null ? 0 : node.left.val;
        int rn = node.right == null ? 0 : node.right.val;
        dfs2(list, node.left, depth + 1, sums, ln + rn);
        dfs2(list, node.right, depth + 1, sums, ln + rn);

    }
    private static void dfs(List<List<Integer>> list,  TreeNode node, int depth){
        if (depth >= list.size())
            return;
        if (node == null){
            list.get(depth).add(0);
            return;
        }
        list.get(depth).add(node.val);
        dfs(list, node.left, depth + 1);
        dfs(list, node.right, depth + 1);
    }

    private static int getDepth(TreeNode node, int depth){
        if (node == null){
            return depth;
        }
        return Math.max(getDepth(node.left, depth + 1), getDepth(node.right, depth + 1));
    }
}
